피보나치 수

3. 정의

'''피보나치 수''' $F\_n$는 0번째 항을 0, 1번째 항을 1로 두고, 2번째 항부터는 바로 앞의 두 항의 합으로 정의되는 수열이다. 즉, 다음과 같은 점화식으로 정의된다.

:$F\_0=0$

:$F\_1=1$

:$F\_n=F\_\{n-1\}+F\_\{n-2\}\backslash qquad(n\backslash geqq\; 2)$

(때로는 $F\_1=1,\; F\_2=1$로 정의하기도 한다.)

피보나치 수의 처음 몇 항은 다음과 같다.

:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ...

이 수열은 1202년 레오나르도 피보나치(Leonardo Fibonacci)가 저술한 『산반서』(Liber Abaci)에 소개되면서 '피보나치 수'라는 이름으로 널리 알려졌다. 하지만 그보다 앞서 인도의 학자 헤마찬드라(Hemachandra)가 운율 연구 과정에서 이 수열을 발견하여 기록한 바 있다.^[1][2]

레오나르도 피보나치는 『산반서』에서 다음과 같은 문제를 통해 이 수열을 설명했다.^[3]

• 한 쌍의 토끼는 태어난 지 2개월 후부터 매달 암수 한 쌍의 토끼를 낳는다.
• 토끼는 죽지 않는다고 가정한다.
• 이 조건에서 갓 태어난 한 쌍의 토끼는 1년 후에 총 몇 쌍으로 불어나는가?

3. 1. 일반항

3. 2. 행렬 표현

4. 성질

피보나치 수는 여러 흥미로운 항등식을 만족한다. 대표적인 것으로 '''카시니 항등식'''(Cassini's identity^영어)이 있다.

:$F\_\{n+1\}F\_\{n-1\}-\{F\_n\}^2=(-1)^n$

또한, '''도가뉴 항등식'''(d'Ocagne's identity^영어)도 성립한다.^[20]

:$F\_\{m+n\}=F\_\{m-1\}F\_n+F\_mF\_\{n+1\}$

황금비 $\backslash varphi$와 관련된 다음과 같은 항등식도 성립한다.^[20]

:$\backslash varphi^n=F\_n\backslash varphi+F\_\{n-1\}$

피보나치 수는 점화식을 이용해 음의 정수 항으로 확장할 수 있다. 이 경우, 다음과 같은 관계가 성립한다.^[20]

:$F\_\{-n\}=(-1)^\{n+1\}F\_n$

4. 1. 급수 공식

4. 2. 생성 함수

4. 3. 수론적 성질

• ''m''이 ''n''으로 나누어 떨어지면, ''F''_''m''은 ''F''_''n''으로 나누어 떨어진다.
• ''F''_''m''이 짝수가 되는 것은 ''m''이 3의 배수일 때와 동치이다.
• ''F''_''m''이 5의 배수가 되는 것은 ''m''이 5의 배수일 때와 동치이다.
• ''p''가 2도 5도 아닌 소수일 때, ''m'' = ''p'' − (5/''p'')라고 하면 ''p''는 ''F''_''m''을 나눈다. 여기서 ( / )는 르장드르 기호이다.

• 제곱수인 피보나치 수는 ''F''₁ = ''F''₂ = 1, ''F''₁₂ = 144 뿐이다 (Cohn 1964)^[4].
• 세제곱수인 피보나치 수는 ''F''₁ = ''F''₂ = 1, ''F''₆ = 8 뿐이다 (London and Finkelstein 1969)^[5].
• 거듭제곱수인 피보나치 수는 위의 제곱수와 세제곱수 외에는 존재하지 않는다 (Bugeaud, Mignotte, Siksek 2006)^[6]. (OEIS A227875)
• 소수인 피보나치 수는 2, 3, 5, 13, 89, 233, 1597, 28657, … 등이 있으며 (OEIS A005478), 이들을 피보나치 소수라고 부른다.
• 삼각수인 피보나치 수는 1, 3, 21, 55 (OEIS A039595) 뿐이다. 이는 Vern Hoggatt에 의해 추측되었고, 나중에 Luo Ming에 의해 증명되었다^[7].
• 하샤드 수인 피보나치 수는 1, 2, 3, 5, 8, 21, 144, 2584, … 등이 있다 (OEIS A117774).
• 피보나치 수는 완전수가 될 수 없다^[8]. 더 나아가, 피보나치 수는 배적 완전수도 될 수 없으며^[9], 두 피보나치 수의 비 또한 완전수가 될 수 없다^[10].

5. 여러 가지 예시

피보나치 수열의 점화식은 다음과 같이 행렬로 표현할 수 있다.^[3]

:$\backslash begin\{bmatrix\}\; F\_\{n+1\}\; \backslash \backslash F\_\{n\}\; \backslash end\{bmatrix\}\; =\; \backslash begin\{bmatrix\}$

1 & 1 \\

1 & 0

\end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix},\;\;\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}

이를 반복하여 적용하면 다음과 같은 행렬 관계식을 얻는다.

:$\backslash begin\{align\}$

\begin{bmatrix}

F_{n+1} & F_{n} \\

F_{n} & F_{n-1}

\end{bmatrix} &= \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}\begin{bmatrix}

F_{n} & F_{n-1} \\

F_{n-1} & F_{n-2}

\end{bmatrix} \\

&= \cdots \\

&= \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}^n\begin{bmatrix}

F_{1} & F_{0} \\

F_{0} & F_{-1}

\end{bmatrix} \\

&= \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}^n\begin{bmatrix}

1 & 0 \\

0 & 1

\end{bmatrix}

\end{align}

여기서 $F\_1=1,\; F\_0=0$이며, $F\_\{-1\}=1$은 점화식 $F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\}$에 $n=1$을 대입하여 얻을 수 있다(자세한 내용은 음수 번호로의 확장 참조). 따라서 다음이 성립한다.

:$\backslash therefore$

\begin{align}

\begin{bmatrix}

F_{n+1} & F_{n} \\

F_{n} & F_{n-1}

\end{bmatrix} = \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}^n

\end{align}

또한, 위 행렬 관계식에서 $n$을 $2n$으로 치환하면,

:$\backslash begin\{align\}$

\begin{bmatrix}

F_{2n+1} & F_{2n} \\

F_{2n} & F_{2n-1}

\end{bmatrix} &= \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}^{2n} = \left ( \begin{bmatrix}

1 & 1 \\

1 & 0

\end{bmatrix}^n \right )^2 = \begin{bmatrix}

F_{n+1} & F_n \\

F_n & F_{n-1}

\end{bmatrix}^2 \\

&= \begin{bmatrix}

F_{n+1}^2 + F_n^2 & F_n(F_{n+1} + F_{n-1}) \\

F_n(F_{n+1} + F_{n-1}) & F_n^2 + F_{n-1}^2

\end{bmatrix}

\end{align}



따라서, 다음과 같은 항등식을 얻는다.

:$\backslash begin\{align\}$

F_{2n+1} &= F_{n+1}^2 + F_n^2 \\

F_{2n} &= F_n(F_{n+1} + F_{n-1}) = F_n(F_n + 2F_{n-1}) \\

F_{2n-1} &= F_n^2 + F_{n-1}^2

\end{align}



피보나치 수열의 모 생성 함수는 다음과 같다.

:$g(x)\; =\; \backslash sum\backslash limits\_\{n=0\}^\{\backslash infty\}\; F\_n\; x^n\; =\; \backslash dfrac\{x\}\{1-x-x^2\}$

또한, 행렬 표현을 기반으로 다음과 같은 점화식을 생각할 수도 있다.

:$\backslash begin\{cases\}$

F_0 = 0 & \, \\

F_1 = 1 & \, \\

F_n = F_q^2+\{ 1+(-1)^n \}F_{q-1}F_q+\dfrac{1-(-1)^n}{2}F_{q+1}^2 &\left( n\geqq 2,\;q=\left\lfloor \dfrac{n}{2} \right\rfloor \right)

\end{cases}



피보나치 수열은 재귀 처리의 예시로 자주 소개된다. 다음은 파이썬에서의 예시이다.

(단, 아래 구현 예시 중 음수 번째 항으로의 확장에 대응하는 것은 예시 5, 예시 6뿐이다.)

5. 1. 자연 속의 피보나치 수열

5. 2. 금융 분야

6. 유사 수열

피보나치 수열은 그 정의, 즉 초기값이나 점화식을 약간 변경하여 다양한 유사 수열을 만들 수 있다. 예를 들어, 각 항이 바로 앞 두 항의 합으로 결정되는 규칙 대신, 더 많은 이전 항들의 합으로 새로운 항을 정의하는 방식으로 일반화할 수 있다. 또한, 수열의 시작 값인 처음 몇 개의 항을 다르게 설정하여 또 다른 종류의 유사 수열을 만들 수도 있다. 이러한 방식으로 생성된 수열들은 피보나치 수열과 유사한 성질을 가지면서도 독특한 특징을 나타낸다.

6. 1. 항 수 변경

• 1-fil형: 처음 ''k''-1개 항을 모두 1로 설정한다.

• 0-fil형: 마지막 항인 (''k''-1)번째 항만 1로 설정하고, 그 앞의 항들은 모두 0으로 설정한다.

특히 ''k''=3인 경우, 즉 바로 앞 세 항의 합으로 각 항이 정해지는 '''트리보나치 수열'''(Tribonacci sequence)은 피보나치 수열 다음으로 많이 연구된다. 0-fil형으로 0번째 항부터 시작하는 트리보나치 수열($T\_n$)은 다음과 같이 정의된다.

:$T\_0\; =\; 0,\; T\_1\; =\; 0,\; T\_2\; =\; 1$

:$T\_\{n+3\}\; =\; T\_n\; +\; T\_\{n+1\}\; +\; T\_\{n+2\}\; \backslash quad\; (n\; \backslash ge\; 0)$

이 수열의 처음 몇 항은 다음과 같다.

:0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (OEIS A000073)

트리보나치 수열의 일반항은 3차 방정식 $x^3\; -\; x^2\; -\; x\; -\; 1\; =\; 0$의 세 해 $\backslash alpha,\; \backslash beta,\; \backslash gamma$를 이용하여 다음과 같이 나타낼 수 있다.

:$T\_n\; =\; \backslash frac\{\backslash alpha^n\}\{(\backslash alpha\; -\; \backslash beta)(\backslash alpha\; -\; \backslash gamma)\}+\; \backslash frac\{\backslash beta^n\}\{(\backslash beta\; -\; \backslash gamma)(\backslash beta\; -\; \backslash alpha)\}+\; \backslash frac\{\backslash gamma^n\}\{(\backslash gamma\; -\; \backslash alpha)(\backslash gamma\; -\; \backslash beta)\}$

여기서 세 해는 다음과 같다.

:$\backslash begin\{align\}$

\alpha &= \frac{1}{3} \left(1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}\right) \\

\beta &= \frac{1}{3} \left(1 + \omega \sqrt[3]{19-3\sqrt{33}} + \bar{\omega} \sqrt[3]{19+3\sqrt{33}}\right) \\

\gamma &= \frac{1}{3} \left(1 + \bar{\omega} \sqrt[3]{19-3\sqrt{33}} + \omega \sqrt[3]{19+3\sqrt{33}}\right)

\end{align}

(단, $\backslash omega\; =\; \backslash frac\{-1\; +\; \backslash sqrt\{3\}\; i\}\{2\}$는 1의 허수 세제곱근이다.)

이때 실수 해 $\backslash alpha\; \backslash approx\; 1.839286755214161\backslash cdots$를 '''트리보나치 상수'''라고 부른다. 이는 피보나치 수열의 황금비에 해당하는 상수로, 트리보나치 수열에서 인접한 두 항의 비는 ''n''이 커짐에 따라 트리보나치 상수로 수렴한다.

:$\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; \backslash frac\{T\_n\}\{T\_\{n-1\}\}\; =\; \backslash alpha$

''k''=4인 경우, 즉 바로 앞 네 항의 합으로 정해지는 '''테트라나치 수열'''(Tetranacci sequence)도 알려져 있다. 0-fil형으로 0번째 항부터 시작하는 테트라나치 수열($T\_n$)은 다음과 같이 정의된다.

:$T\_0\; =\; 0,\; T\_1\; =\; 0,\; T\_2\; =\; 0,\; T\_3\; =\; 1$

:$T\_\{n+4\}\; =\; T\_n\; +\; T\_\{n+1\}\; +\; T\_\{n+2\}\; +\; T\_\{n+3\}\; \backslash quad\; (n\; \backslash ge\; 0)$

이 수열의 처음 몇 항은 다음과 같다.

: 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS A000078)

테트라나치 수열의 일반항은 사차 방정식 $x^4\; -\; x^3\; -\; x^2\; -\; x\; -\; 1\; =\; 0$의 네 해 $\backslash alpha,\; \backslash beta,\; \backslash gamma,\; \backslash delta$를 이용하여 다음과 같이 나타낼 수 있다.

:$T\_n\; =\; \backslash frac\{\backslash alpha^n\}\{(\backslash alpha-\; \backslash beta)(\backslash alpha\; -\; \backslash gamma)(\backslash alpha\; -\; \backslash delta)\}+\; \backslash frac\{\backslash beta^n\}\{(\backslash beta\; -\; \backslash gamma)(\backslash beta\; -\; \backslash delta)(\backslash beta\; -\; \backslash alpha)\}+\; \backslash frac\{\backslash gamma^n\}\{(\backslash gamma\; -\; \backslash delta)(\backslash gamma\; -\; \backslash alpha)(\backslash gamma\; -\; \backslash beta)\}+\; \backslash frac\{\backslash delta^n\}\{(\backslash delta\; -\; \backslash alpha)(\backslash delta\; -\; \backslash beta)(\backslash delta\; -\; \backslash gamma)\}$

6. 2. 초기값 변경

7. 프로그래밍 구현 (파이썬)

피보나치 수는 재귀 처리의 예시로 자주 소개된다. 다음은 파이썬을 이용한 다양한 구현 예시이다.

=== 재귀적 구현 ===

가장 기본적인 방법은 피보나치 수의 정의를 그대로 코드로 옮긴 재귀 함수를 사용하는 것이다. 0번째 항부터 시작하는 경우, 코드는 다음과 같다.



def fib(n):

if n == 0 or n == 1:

return n

return fib(n-2) + fib(n-1)



또는 타입 힌트를 사용하여 다음과 같이 작성할 수도 있다.



def fib(n: int) -> int:

if n < 2:

return n

else:

return fib(n=n-1) + fib(n=n-2)



그러나 이 방식은 ''n''이 주어졌을 때 ''F_n''을 구하기까지 ''F_n'' ∝ ''φⁿ'' (여기서 ''φ''는 황금비) 번의 함수 호출이 발생하여 지수 시간 복잡도를 가진다. 즉, ''n''이 조금만 커져도 계산 시간이 매우 길어져 실용적이지 않다.

=== 메모이제이션을 이용한 재귀적 구현 ===

재귀적 구현의 비효율성을 개선하기 위해 메모이제이션 기법을 사용할 수 있다. 이미 계산된 피보나치 수 값을 저장해두고, 필요할 때 다시 계산하는 대신 저장된 값을 사용하는 방식이다.



memo = {}

def fib(n):

if n == 0 or n == 1:

return n

if n not in memo:

memo[n] = fib(n-2) + fib(n-1)

return memo[n]



파이썬의 `functools` 모듈에 있는 `cache` 데코레이터를 사용하면 더 간편하게 메모이제이션을 구현할 수 있다.



from functools import cache

@cache

def fib(n: int) -> int:

if n < 2:

return n

else:

return fib(n=n-1) + fib(n=n-2)



메모이제이션을 사용하면 각 피보나치 수는 한 번만 계산되므로 선형 시간 복잡도로 계산할 수 있다.

=== 반복적 구현 ===

반복문을 사용하여 피보나치 수를 계산할 수도 있다. 이 방법은 재귀 호출의 오버헤드가 없고 메모리 사용량도 적어 효율적이다.



def fib(n: int) -> int:

a, b = 1, 0 # F_1, F_0 에 해당하는 값으로 시작 (n=0일 때 b=0 반환)

for _ in range(n):

a, b = b, a+b # 다음 항 계산 (b가 F_k, a+b가 F_{k+1}이 됨)

return b # n번 반복 후 b는 F_n이 됨



이 구현 역시 선형 시간 복잡도를 가진다.

=== 꼬리 재귀 형태의 구현 ===

일부 언어에서는 꼬리 재귀 최적화를 지원하지만, 표준 파이썬 인터프리터는 이를 지원하지 않는다. 그러나 꼬리 재귀와 유사한 형태로 함수를 작성하여 반복적인 계산 과정을 표현할 수 있다. 이 방식은 추가적인 인자를 사용하여 상태를 전달한다.



def fib(n: int, a: int = 1, b: int = 0) -> int:

# a는 F_{k+1}, b는 F_k 에 해당하는 값을 가짐

if n == 0:

return b # n번 반복 후 b는 F_n

else:

# 다음 단계로 상태 업데이트 (a -> b, b -> a+b)

return fib(n=n-1, a=b, b=a+b)



이 함수는 ''n''이 1 이상일 때, 호출 횟수를 ''n'' 회로 제한하여 선형 시간으로 처리할 수 있다.

=== 행렬 표현을 이용한 구현 ===

피보나치 수열의 점화식은 다음과 같이 행렬로 표현할 수 있다.^[3]

:

이를 반복 적용하면 다음 관계식을 얻는다.

:

여기서 ''n''을 ''n'' - 1로 치환하면,

:

따라서 ''F_n''은 행렬 의 좌상단 성분과 같다. 행렬의 거듭제곱은 분할 정복 알고리즘을 이용하여 로그 시간에 계산할 수 있으므로, 이를 이용하면 피보나치 수를 매우 빠르게 계산할 수 있다. SymPy 라이브러리를 사용한 예시는 다음과 같다.



from sympy import Matrix

def fib(n: int) -> int:

if n == 0: # 행렬 거듭제곱은 n-1을 사용하므로 n=0 예외 처리

return 0

# (n-1) 거듭제곱 계산 후 좌상단 성분 반환

return (Matrix(1, 1], [1, 0) ** (n - 1))[0, 0]



또한, 행렬 표현에서 유도된 다음 점화식을 사용하여 재귀적으로 구현할 수도 있다. 이 방식은 재귀 호출 횟수를 줄여 대수 시간(로그 시간) 복잡도를 가진다.

:

이를 코드로 구현하면 다음과 같다. 단, 프로그램 상에서는 0을 곱하는 경우에도 해당 값의 계산이 생략되지 않으므로(단락 평가되지 않음), 조건식을 사용하여 분기한다. 실제 효율적인 사용을 위해서는 메모이제이션이 필수적이다.



# 이 구현은 앞서 정의된 fib 함수에 의존하며, 메모이제이션과 함께 사용해야 효율적이다.

# 여기서는 설명을 위해 독립적인 함수 형태로 제시하며, 실제 사용 시에는 메모이제이션 적용 필요.

memo_fast = {}

def fib_fast(n: int) -> int:

if n in memo_fast:

return memo_fast[n]

if n < 2:

return n

q = n // 2

fq = fib_fast(n=q)

fq_minus_1 = fib_fast(n=q-1) # F_{q-1}

if n % 2 == 0: # n이 짝수일 때 F_n = F_q^2 + 2 * F_{q-1} * F_q

result = fq ** 2 + 2 * fq_minus_1 * fq

else: # n이 홀수일 때 F_n = F_q^2 + F_{q+1}^2

# F_{q+1} = F_q + F_{q-1} 이므로 다시 계산할 필요 없이 사용 가능

fq_plus_1 = fq + fq_minus_1

result = fq 2 + fq_plus_1 2

memo_fast[n] = result

return result

# 초기 호출 예시 (메모이제이션 딕셔너리 초기화 필요)

# memo_fast = {}

# print(fib_fast(10))



'''주의:''' 위 `fib_fast` 코드는 설명을 위한 것이며, 실제 효율적인 사용을 위해서는 `fib_fast` 함수 내에서 재귀 호출 시에도 `fib_fast`를 호출하고, 전역 또는 클래스 멤버 등으로 `memo_fast` 딕셔너리를 관리하여 메모이제이션을 올바르게 적용해야 한다.

=== 일반항을 이용한 구현 ===

비네 공식으로 알려진 피보나치 수의 일반항을 이용하여 계산할 수도 있다.

:$F\_n\; =\; \backslash frac\{\backslash varphi^n\; -\; \backslash psi^n\}\{\backslash sqrt\{5\}\}\; =\; \backslash frac\{\backslash left(\backslash frac\{1+\backslash sqrt\{5\}\}\{2\}\backslash right)^n\; -\; \backslash left(\backslash frac\{1-\backslash sqrt\{5\}\}\{2\}\backslash right)^n\}\{\backslash sqrt\{5\}\}$

여기서 $\backslash varphi\; =\; \backslash frac\{1+\backslash sqrt\{5\}\}\{2\}$는 황금비이고, $\backslash psi\; =\; \backslash frac\{1-\backslash sqrt\{5\}\}\{2\}\; =\; 1\; -\; \backslash varphi\; =\; -\backslash frac\{1\}\{\backslash varphi\}$이다.

부동소수점 연산을 사용하면 계산 오차가 발생할 수 있으므로, 정확한 계산을 위해 파이썬의 `decimal` 모듈을 사용할 수 있다.



from decimal import Decimal, getcontext

# 필요에 따라 정밀도 설정 (예: getcontext().prec = 50)

SQRT5 = Decimal(5).sqrt()

PHI = (1 + SQRT5) / 2 # 황금비

def fib(n: int) -> int:

if n == 0: return 0

# |PSI^n / sqrt(5)|는 n이 커짐에 따라 0에 수렴하며, n >= 1에 대해 0.5보다 작다.

# 따라서 F_n은 PHI^n / sqrt(5) 에 가장 가까운 정수이다.

# F_n = round(PHI**n / SQRT5)

# PSI = -1/PHI 관계를 이용하여 계산할 수도 있다.

return int(round((PHI n - (-PHI) -n) / SQRT5))



또한, 피보나치 수의 일반항은 ''n''의 부호에 따라 두 항 중 하나의 절댓값이 0.5 미만이 되므로, 부호 함수와 바닥 함수를 사용하여 다음과 같이 나타낼 수도 있다.

:$F\_n\; =\; (\backslash operatorname\{sgn\}\; n)\backslash left\backslash lfloor\; \backslash frac\{\backslash \{\; (\backslash operatorname\{sgn\}\; n)\backslash varphi\; \backslash \}^$